package leetcode每日一题;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 1. 问题描述
 *      给你一个由一些多米诺骨牌组成的列表dominoes。
 *      如果其中某一张多米诺骨牌可以通过旋转 0度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。
 *      形式上，dominoes[i]=[a,b]和dominoes[j]=[c,d]等价的前提是a==c且b==d，或是a==d且b==c。
 *      在0<=i<j<dominoes.length的前提下，找出满足dominoes[i]和dominoes[j]等价的骨牌对(i,j)的数量
 *
 * 2. 算法分析
 *      1. 暴力法   超出时间限制
 *      2.
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 等价多米诺骨牌的等价数量 {
    public static void main(String[] args) {
        int[] a = {1,2};
        int[] b = {2,1};
        Arrays.sort(b);
        System.out.println(a == b);
    }

    // 暴力法  超出时间限制
    public int numEquivDominoPairs1(int[][] dominoes) {
        int count = dominoes.length;
        if(count <= 1) {
            return 0;
        }
        int res = 0;
        for(int i = 0; i < count; i++) {
            for(int j = i + 1; j < count; j++) {
                if(isEquvilence(dominoes[i],dominoes[j])) {
                    res++;
                }
            }
        }
        return res;
    }
    // 判断是否等价
    public boolean isEquvilence(int[] dominoe1,int[] dominoe2) {
        boolean flag1 = dominoe1[0] == dominoe2[0] && dominoe1[1] == dominoe2[1];
        boolean flag2 = dominoe1[0] == dominoe2[1] && dominoe1[1] == dominoe2[0];
        return flag1 || flag2;
    }


    // 将二维转化为一维(降维法)
    // 由于每个多米诺骨牌中的数字最大为9，所以我们考虑如下的映射: [x,y] ---> 10x+y
    // 如果[x,y],[y,x](不妨设x < y),此时我们知道如果将[y,x] ---> [x,y] ---> 10x+y 这样等价的条件转化为整形是否一致
    // 此时我们就可以不需要实现哈希表，减少了空间复杂度
    public int numEquivDominoPairs2(int[][] dominoes) {
        int[] freq = new int[100]; // 因为最大值为99，所以我们设置一个长度为100的数组，存放每种映射之后的整形数字出现的频数
        int count = 0; // 定义计数器
        for (int[] dominoe : dominoes) {
            if(dominoe[0] > dominoe[1]) {
                int temp = dominoe[0];
                dominoe[0] = dominoe[1];
                dominoe[1] = temp;
            }
            int num = dominoe[0] * 10 + dominoe[1];

            // 如何理解这行代码？
            /**
             * 如果按照正常的算法，如果出现了n个等价的多米诺，他们的组合为C(n,2) = n*(n-1)/2 = 1 + 2 + 3 + ... + n-1
             * 如果当前[x,y] 第一次出现 此时freq[num] = 0 此时count += 0
             * 如果出现[x,y] 的等价是，此时的freq[num] = 1 此时 count += 1
             * 假设第k次出现[x,y] 的等价，此时 freq[num] = k - 1 此时的count += k-1
             * 依次类推，即我们将乘法转化为加法
             * 所以count += freq[num] 最终可以求出所有的等价对数
             */
            count += freq[num];
            freq[num]++; // 频数+1
        }
        return count;
    }


}
